package simple;

import java.util.*;

/**
 在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）


 数据范围：0 \le n \le 100000≤n≤10000，且字符串只有字母组成。
 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 示例1
 输入：
 "google"
 返回值：
 4
 示例2
 输入：
 "aa"
 返回值：
 -1

 *
 * @author WangZhiJian
 * @since 2022/1/14
 */
public class 第一个只出现一次的字符 {

    /**
     * 运行时间：121ms
     * 超过0.51% 用Java提交的代码
     * 占用内存：15600KB
     * 超过0.77%用Java提交的代码
     * @param str
     * @return
     */
    public static int FirstNotRepeatingChar(String str) {
        // 黑名单
        Set<Character> blackList = new HashSet<>();
        // 存在map
        Map<Character, Integer> existingMap = new LinkedHashMap<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            // 黑名单存在直接跳过
            if(blackList.contains(c))
                continue;
            // 移除并加入黑名单
            if(existingMap.containsKey(c)){
                existingMap.remove(c);
                blackList.add(c);
                continue;
            }
            // 标记地址
            existingMap.put(c,i);
        }

        return existingMap.entrySet().stream().map(Map.Entry::getValue).findFirst().orElse(-1);
    }

    public static void main(String[] args) {
        System.out.println(FirstNotRepeatingChar("google"));
    }
}
